// 实现二叉搜索树，每个节点最多有两个节点，一个左侧节点一个右侧节点，左侧节点存放比父节点小的值，右侧节点存储比父节点大的值

// 实现键（节点）类

class Node {
  constructor(key) {
    this.key = key
    this.left = null
    this.right = null
  }
}
function defaultCompare(a, b) {
  if (a > b) {
    return 'big_than'
  } else if (a < b) {
    return 'less_than'
  }
}

// const Compare = { 
//   LESS_THAN: -1, 
//   BIGGER_THAN: 1 
//  };
// function defaultCompare(a, b) { 
//   if (a === b) { // {1} 
//   return 0; 
//   } 
//   return a < b ? Compare.LESS_THAN : Compare.BIGGER_THAN; // {2} 
//  } 

class BinarySearchTree {
  constructor(compareFn = defaultCompare) {
    this.compareFn = compareFn
    this.root = null
  }
  insert(key) {
    if (this.root == null) {
      this.root = new Node(key)
    } else {
      this.insertNode(this.root, key)
    }

  }
  insertNode(node, key) { // 找到新节点应该插入的正确位置
    if (this.compareFn(key, node.key) === 'less_than') {
      if (node.left == null) {
        node.left = new Node(key)
      } else {
        this.insertNode(node.left, key)
      }
    } else {
      if (node.right == null) {
        node.right = new Node(key)
      } else {
        this.insertNode(node.right, key)
      }
    }
  }
  search(key) { // key存在返回true不存在返回false
    return this.searchNode(this.root, key)
  }
  searchNode(node, key) {
    if (node == null) return false // 递归的基线条件，表示已经递归的外部节点了不用在往下递归了
    if (this.compareFn(key, node.key) === 'less_than') {
      return this.searchNode(node.left, key)
    } else if (this.compareFn(key, node.key) === 'big_than') {
      return this.searchNode(node.right, key)
    } else {
      return true
    }
  }
  inOrderTraverse(callback) {// 中序遍历
    this.inOrderTraverseNode(this.root, callback)
  }
  inOrderTraverseNode(node, callback) {
    if (node != null) {
      this.inOrderTraverseNode(node.left, callback);
      callback(node.key)
      this.inOrderTraverseNode(node.right, callback)
    }
  }
  preOrderTraverse(callback) {// 先序遍历
    this.preOrderTraverseNode(this.root, callback)
  }
  preOrderTraverseNode(node, callback) {
    if (node != null) {
      callback(node.key)
      this.preOrderTraverseNode(node.left, callback);
      this.preOrderTraverseNode(node.right, callback)
    }
  }
  postOrderTraverse(callback) {// 后序遍历
    this.postOrderTraverseNode(this.root, callback)
  }
  postOrderTraverseNode(node, callback) {
    if (node != null) {
      this.postOrderTraverseNode(node.left, callback)
      this.postOrderTraverseNode(node.right, callback)
      callback(node.key)
    }
  }
  min() {// 返回树中最小值
    return this.minNode(this.root)
  }
  minNode(node) {
    let current = node;
    while (current != null && current.left != null) {
      current = current.left
    }
    return current
  }
  max() {
    return this.maxNode(this.root)
  }
  maxNode(node) {
    let current = node;
    while (current != null && current.right != null) {
      current = current.right
    }
    return current
  }
  remove(key) {// 移出key
    this.root = this.removeNode(this.root, key)
  }
  removeNode(node, key) {
    if (node == null) {
      return null
    }
    if (this.compareFn(key, node.key) === 'less_than') {
      node.left = this.removeNode(node.left, key)
      return node;
    } else if (this.compareFn(key, node.key) === 'big_than') {
      node.right = this.removeNode(node.right, key)
      return node;
    } else {
      if (node.right == null && node.left == null) {
        node = null
        return node
      }
      if (node.left == null) {
        node = node.right
        return node
      } else if (node.right == null) {
        node = node.left
        return node
      }

      let aux = this.minNode(node.right);
      node.key = aux.key;
      node.right = this.removeNode(node.right, aux.key)
      return node
    }
  }
}

let tree = new BinarySearchTree()
tree.insert(11)
tree.insert(7);
tree.insert(15);
tree.insert(5);
tree.insert(3);
tree.insert(9);
tree.insert(8);
tree.insert(10);
tree.insert(13);
tree.insert(12);
tree.insert(14);
tree.insert(20);
tree.insert(18);
tree.insert(25);
tree.insert(6);

// let callback = (key) => console.log(key)
// tree.inOrderTraverse(callback)
// console.log(tree.max())
tree.max()
// tree.search(25)
// console.log(tree.search(100))
tree.remove(25)
console.log(tree)
// tree.preOrderTraverse(callback)
// tree.postOrderTraverse(callback)